//1017.负二进制转换
//https://leetcode.cn/problems/convert-to-base-2
class Solution {
public:
    string baseNeg2(int n) {
        if(n <= 1) return to_string(n);
        string ret;
        const int base = -2;
        while(n)
        {
            int rem = n%base; //求余数 类似于n&1
            n /= base;
            if(rem < 0) //余数为-1 二进制中没有-1
            {
                //根据公式 n = base^商+rem
                //也就说n由2的多少倍加上余数得来
                //当rem为-1时 将rem变为1需要+2
                //等式两边同时+2  则n+2=2*base-1+2
                //n+1=2*base 所以rem变为1时商需要+1此时等式值不变
                rem = 1; //转换为1  此时相对于+2 所以商需要+1抵消
                n += 1;  //之所以+1是因为
            }
            ret.push_back('0'+rem);
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};
 